package dp;


/**
 * https://leetcode.cn/problems/unique-binary-search-trees/?favorite=2cktkvj
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493429&idx=1&sn=4745d7ac1891fe6ab666f63ccbc56a1d&chksm=9bd4193daca3902b8d717ab5e047f128b6fc94f0afa9340ef2f723038ef2b690e9f04778d8dc&scene=178&cur_album_id=2165105273311494144#rd
 */
public class _96_不同的二叉搜索树 {

    int meno[][];

    public int numTrees(int n) {
        if (n == 0) return 0;
        meno = new int[n + 1][n + 1];
        return dp(1, n);
    }


    private int dp(int lo, int ro) {
        int result = 0;
        if (lo > ro) return 1;

        if (meno[lo][ro] != 0) return meno[lo][ro];

        for (int middle = lo; middle <= ro; middle++) {
            int left = dp(lo, middle - 1);
            int right = dp(middle + 1, ro);
            result += left * right;
        }

        meno[lo][ro] = result;

        return result;
    }
}
